class Solution {
public:
    bool dp[110][110];
    bool isInterleave(string s1, string s2, string s3) {
        int n = s1.size(), m = s2.size(), k = s3.size();
        s1 = ' ' + s1;
        s2 = ' ' + s2;
        s3 = ' ' + s3;
        
        if (n + m != k) return false;
        dp[0][0] = true;
        // init 
        for (int i = 1; i <= n; i ++ ) 
            if (s1[i] == s3[i]) 
                dp[i][0] = dp[i - 1][0];
        
        for (int i = 1; i <= m; i ++ ) 
            if (s2[i] == s3[i]) 
                dp[0][i] = dp[0][i - 1];
        
        
        for (int i = 1; i <= n; i ++ ) {
            for (int j = 1; j <= m; j ++ ) {
                dp[i][j] = dp[i - 1][j] && s1[i] == s3[i + j] || dp[i][j - 1] && s2[j] == s3[i + j];
            }
        }
        return dp[n][m];
    }
};
